public class Solution52 {
    int n;
    int res = 0;
    int[] directArrX = new int[]{1,1,-1,-1};
    int[] directArrY = new int[]{1,-1,-1,1};

    private int[][] doCopy(int[][] occur){
        int[][] copyOccur = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                copyOccur[i][j] = occur[i][j];
            }
        }
        return copyOccur;
    }

    private int[][] occurArr(int rowNum, int colNum, int[][] occur){
        int[][] copyOccur = doCopy(occur);
        for (int i = 0; i < n; i++) {
            copyOccur[i][colNum] = 1;
        }
        for (int i = 0; i < n; i++) {
            copyOccur[rowNum][i] = 1;
        }
        for (int i = 0; i < 4; i++) {
            int directX = directArrX[i];
            int directY = directArrY[i];
            for (int j = 1;; j++) {
                int tmpX = colNum + (directX*j);
                int tmpY = rowNum + (directY*j);
                if((0<=tmpX&&tmpX<n)&&(0<=tmpY&&tmpY<n)){
                    copyOccur[tmpY][tmpX] = 1;
                }
                else{
                    break;
                }
            }
        }
        return copyOccur;
    }

    private void travel(int rowNum, int[][] occur){
        if(rowNum == n){
            res++;
            return;
        }
        int[] tmpRow = occur[rowNum];
        for (int i = 0; i < tmpRow.length; i++) {
            int status = tmpRow[i];
            if(status == 0){
                int[][] tmpOccur = occurArr(rowNum, i, occur);
                travel(rowNum+1, tmpOccur);
            }
        }
    }

    public int totalNQueens(int n) {
        this.n = n;
        travel(0, new int[n][n]);
        return res;
    }
}
